package LeetCode;

public class LC_633_SumofSquareNumbers {

    public static void main(String[] args) {

    }

    public class Solution_1 {
        public boolean judgeSquareSum(int c) {
            for (long a = 0; a * a <= c; a++) {
                double b = Math.sqrt(c - a * a);
                if (b == (int) b)
                    return true;
            }
            return false;
        }
    }

    public class Solution_2 {
        public boolean judgeSquareSum(int c) {
            for (long a = 0; a * a <= c; a++) {
                int b = c - (int) (a * a);
                if (binary_search(0, b, b))
                    return true;
            }
            return false;
        }

        boolean binary_search(long s, long e, int n) {
            if (s > e)
                return false;
            long mid = s + (e - s) / 2;
            if (mid * mid == n)
                return true;
            if (mid * mid > n)
                return binary_search(s, mid - 1, n);
            return binary_search(mid + 1, e, n);
        }
    }


    public class Solution_3 {
        public boolean judgeSquareSum(int c) {
            for (int i = 2; i * i <= c; i++) {
                int count = 0;
                if (c % i == 0) {
                    while (c % i == 0) {
                        count++;
                        c /= i;
                    }
                    if (i % 4 == 3 && count % 2 != 0)
                        return false;
                }
            }
            return c % 4 != 3;
        }
    }

}